package com.lx.algorithm.temp;

import com.leetCode.tree.TreeNode;

/**
 * Description:
 * Copyright:   Copyright (c)2019
 * Company:     zefu
 *
 * @author: 张李鑫
 * @version: 1.0
 * Create at:   2021-11-23 01:03:01
 * <p>
 * Modification History:
 * Date         Author      Version     Description
 * ------------------------------------------------------------------
 * 2021-11-23     张李鑫                     1.0         1.0 Version
 */
public class LowestCommonAncestor {
    /**
     * 给定一棵二叉树(保证非空)以及这棵树上的两个节点对应的val值 o1 和 o2，请找到 o1 和 o2 的最近公共祖先节点。
     * <p>
     * 数据范围：1 \le n \le 10001≤n≤1000，树上每个节点的val满足 0<val \le 1000<val≤100
     * 要求：空间复杂度 O(1)O(1)，时间复杂度 O(n)O(n)
     */


    public static class Info {
        boolean hasA;
        boolean hasB;
        Integer node;


        public Info(boolean hasA, boolean hasB, Integer node) {
            this.hasA = hasA;
            this.hasB = hasB;
            this.node = node;
        }
    }


    public int lowestCommonAncestor(TreeNode root, int o1, int o2) {
        // write code here
        return process(root, o1, o2).node;
    }

    private static Info process(TreeNode root, int o1, int o2) {
        if (root == null) {
            return new Info(false, false, null);
        }
        Info leftInfo = process(root.left, o1, o2);
        Info rightInfo = process(root.right, o1, o2);


        if (leftInfo.node != null || rightInfo.node != null) {
            return leftInfo.node == null ? rightInfo : leftInfo;
        }

        boolean hasA = leftInfo.hasA || rightInfo.hasA;
        boolean hasB = leftInfo.hasB || rightInfo.hasB;


        if (root.val == o1) {
            hasA = true;
        }

        if (root.val == o2) {
            hasB = true;
        }

        Integer node = (hasA && hasB) ? root.val : null;
        return new Info(hasA, hasB, node);
    }


}